//优先队列
#ifndef __PRIORITYQUEUE__HPP
#define __PRIORITYQUEUE__HPP

#include"LinkedQueue.hpp"

namespace NgSiuKei {

template<class TheClass>
class PriorityQueue: public LinkedQueue<TheClass> {
    public:
    PriorityQueue(void);
    ~PriorityQueue(void);

    public:
    //入队列
    void push(const TheClass val);
    //打印队列
    void print(void) const;
};

template<class TheClass>
PriorityQueue<TheClass>::PriorityQueue(void) {
}

template<class TheClass>
PriorityQueue<TheClass>::~PriorityQueue(void) {
}

template<class TheClass>
void PriorityQueue<TheClass>::push(const TheClass val) {
    lq_node<TheClass> *newNode = new lq_node<TheClass>;
    newNode->val = val;
    newNode->prev = nullptr;
    newNode->next = nullptr;
    if(this->isEmpty()) {
        this->front = newNode;
        this->rear = newNode;
        this->front->prev = nullptr;
    }
    else if(this->front->val >= val) { //当所有元素比val大，插队头
        newNode->next = this->front;
        this->front->prev = newNode;
        this->front = newNode;
    }
    else if(this->rear->val < val) { //当所有元素比val小，插队尾
        newNode->prev = this->rear;
        this->rear->next = newNode;
        this->rear = newNode;
    }
    else { //插中间
        lq_node<TheClass> *currentNode = this->front;
        lq_node<TheClass> *smallerNode = nullptr;
        lq_node<TheClass> *biggerNode = nullptr;
        
        //寻找相邻的一对分别比自己大与小的节点
        while(nullptr != currentNode) {
            if(currentNode->val < val) {
                smallerNode = currentNode;
            }
            if(currentNode->val >= val) {
                biggerNode = currentNode;
                break;
            }
            currentNode = currentNode->next;
        }

        //插入
        newNode->prev = smallerNode;
        newNode->next = biggerNode;
        smallerNode->next = newNode;
        biggerNode->prev = newNode;
    }
    this->size++;
}


template<class TheClass>
void PriorityQueue<TheClass>::print(void) const {
    cout << "打印优先队列：[ ";
    lq_node<TheClass> *currentNode = this->front;
    while(nullptr != currentNode) {
        cout << currentNode->val << ' ';
        currentNode = currentNode->next;
    }
    cout << ']' << endl;
}

}

#endif